1) Field of the Invention
The present invention relates to a method and an apparatus for calculating an average of two parity protected binary numbers.
2) Description of the Related Art
Calculating an average (hereinafter, “averaging”) two sets of data is a basic process in image processing for MPEG (Motion Picture Expert Group) and DVD (digital versatile disk). With the widespread use of digital imaging, quick data averaging is desired.
FIG. 9A illustrates a basic averaging process. Two 16-bit binary numbers X<15:00> and Y<15:00> are rounded off to obtain an average Z<15:00>, where <15:00> denotes 16 bits from “bit 0” to “bit 15”; “bit 0” being the least significant bit, and “bit 15” being the most significant bit. The basic averaging process is explained below.                (1) Add X<15:00> and Y<15:00> to obtain Z′<16:00>.        (2) Divide Z′ by 2. It is known that shifting a binary number to the right by one bit divides the binary number by 2. Therefore, shift Z′ to the right by one bit to obtain Z″<15:−1>.        (3) If rounding off method is used, “1” is added to Z″<−1>, and the higher 16 bits Z″<15:00> are used as the average Z<15:00>. The bit in position <−1> is discarded. Whereas, if rounding down method is used, the higher 16 bits Z″<15:00> are used as the average Z<15:00>.        
For example, from X=49834 (decimal)=1100 0010 1010 1010 (binary) and Y=34085 (decimal)=1000 0101 0010 0101 (binary), a rounded-off average of the two numbers, Z=41960 (decimal)=1010 0011 1110 1000 (binary), can be derived by the following procedure.                (1) Add the two numbers.Z′ (decimal)=49834+34085=83919Z′ (binary)=1100 0010 1010 1010+1000 0101 0010 0101=1 0100 0111 1.100 1111        (2) Shift the sum to the right by one bit. In this case, “.” indicates the position of the decimal point.Z″ (decimal)=83919÷2=41959.5Z″ (binary)=1010 0011 1110 0111.1        (3) Add “1” to the first digit after the decimal point for rounding off.Z (decimal)=41959.5+0.5=41960Z (binary)=1010 0011 1110 0111.1+0.1=1010 0011 1110 1000        
FIG. 9B illustrates an averaging circuit for calculating an average by the basic averaging process. An adder 921 inputs two 16-bit data X<15:00> and Y<15:00> and outputs a 17-bit result Z′<16:00>. Then, a shifter 922 shifts Z′ to the right by one and outputs Z″<15:−1>. Finally, a rounding circuit 923 adds “1” to the least significant bit in Z″ for rounding off. Thus, the 16-bit average Z<15:00> is obtained.
Thus, averaging by the basic averaging process requires three arithmetic circuits, the adder 921, the shifter 922 and the rounding circuit 923. This increases processing time and number of arithmetic circuits. Therefore, the averaging process is being improved to reduce processing time and the number of arithmetic circuits.
FIG. 9C illustrates an improved averaging process. In Japanese Patent Application Laid-open No. H 10-105382, two 16-bit binary numbers X<15:00> and Y<15:00> are rounded off to obtain an average Z<15:00>, as explained in the following rounding procedure.                (1) Add X<15:00>, Y<15:00> and “1 ” for rounding off to obtain Z′<16:00>.        (2) Divide Z′ by 2 to obtain an average. It is known that shifting a binary number to the right by one bit divides the binary number by 2. Therefore, shift Z′ to the right by one bit to obtain Z<15:0>. The value of Z<−1> shifted out through the shift process is not included in the result.        
Specifically, like in the previous example, from X=49834 (decimal)=1100 0010 1010 1010 (binary) and Y=34085 (decimal)=1000 0101 0010 0101 (binary), a rounded-off average of the two numbers, Z=41960 (decimal)=1010 0011 1110 1000 (binary), can be derived according to the improved process by the following procedure.                (1) Add two numbers and “1” for rounding. The addition of “1” can be achieved easily by putting “1” on the carry to the least significant bit.Z′ (decimal)=49834+34085+1=83920Z′ (binary)=1100 0010 1010 1010+1000 0101 0010 0101+1=1 0100 0111 1101 0000        (2) Shift the sum to the right by one bit. In this case, “.” indicates the position of the decimal point.Z′ (decimal)=83919÷2=41960Z (binary)=1010 0011 1110 1000.0        
FIG. 9D illustrates an averaging circuit for calculating an average by the improved averaging process. An adder 941 inputs two 16-bit data X<15:00> and Y<15:00> and “1” as the carry to the least significant bit to obtain a 17-bit result Z′<16:00>.
Then, a shifter 942 shifts Z′<16:00> to the right by one bit to obtain the result Z<15:00>. Such an improved process uses two arithmetic circuits, the adder 941 and the shifter 942, to calculate an average. Thus, processing time and number of arithmetic circuits reduce.
On the other hand, in data that can be processed by a computer, parity is added to improve reliability. An averaging circuit for calculating an average of data protected by parity is explained next.
To obtain a parity protected average of two parity protected data, the adder and the shifter in the averaging circuit require an additional circuit for predicting output parity based on input data and input parity. Parity prediction logic in the adder and the shifter is explained below.
The parity prediction logic in the adder is explained first. In this case, two 8-bit input data are represented by X<7:0> and Y<7:0> and their respective parities are given by XP and YP. In the adding operation, if H denotes half-added data at each bit and C denotes a carry to each bit, parity ZP for the sum Z is represented by the following equation. In this equation, “∀” indicates Excusive-OR (xor), “+” indicates logical sum (or), “&” indicates logical product (and), and “^” indicates Inversion (not). The parity in this example is odd parity.
                    ZP        =                ⁢                                           ⋀                    ⁢                      (                          Z              <              7              >                              ∀                                  Z                  <                  6                  >                                      ∀                                          Z                      <                      5                      >                                              ∀                                                  Z                          <                          4                          >                                                      ∀                                                          Z                              <                              3                              >                                                                                                                                                                                                                                              ⁢                  ∀                      Z            <            2            >                          ∀                              Z                <                1                >                                  ∀                                      Z                    <                    0                    >                                                                                      )                                =                ⁢                                           ⋀                    ⁢                      [                                          (                                  H                  <                  7                  >                                      ∀                                          C                      <                      7                      >                                                                      )                            ⁢                              ∀                                                      (                                          H                      <                      6                      >                                              ∀                                                  C                          <                          6                          >                                                                                      )                                    ⁢                                      ∀                                          (                                              H                        <                        5                        >                                                                                                                                                                            ⁢                      ∀                          C              <              5              >                                )                ⁢                  ∀                                    (                              H                <                4                >                                  ∀                                      C                    <                    4                    >                                                              )                        ⁢                          ∀                              (                                  H                  <                  3                  >                                      ∀                                          C                      <                      3                      >                                                                      )                                                                                    ⁢                  ∀                                    (                              H                <                2                >                                  ∀                                      C                    <                    2                    >                                                              )                        ⁢                          ∀                                                (                                      H                    <                    1                    >                                          ∀                                              C                        <                        1                        >                                                                              )                                ⁢                                  ∀                                      (                                          H                      <                      0                      >                                              ∀                        C                                                                                                                                                                            ⁢                      <            0            >                    )                ]                                =                ⁢                                           ⋀                    ⁢                      [                          (                              H                <                7                >                                  ∀                                      H                    <                    6                    >                                          ∀                                              H                        <                        5                        >                                                  ∀                                                      H                            <                            4                            >                                                          ∀                                                              H                                <                                3                                >                                                                                                                                                                                                                                                                                        ⁢                      ∀                          H              <              2              >                              ∀                                  H                  <                  1                  >                                      ∀                                          H                      <                      0                      >                                                                                                    )                ⁢                  ∀                      (                          C              <              7              >                              ∀                                  C                  <                  6                  >                                      ∀                    C                                                                                                                                  ⁢                      <            5            >                          ∀                              C                <                4                >                                  ∀                                      C                    <                    3                    >                                          ∀                                              C                        <                        2                        >                                                  ∀                                                      C                            <                            1                            >                                                          ∀                                                              C                                <                                0                                >                                                                                                                                                                                                                                      )                ]                                =                ⁢                                           ⋀                    ⁢                      [                          [                                                (                                      X                    <                    7                    >                                          ∀                                              Y                        <                        7                        >                                                                              )                                ⁢                                  ∀                                                            (                                              X                        <                        6                        >                                                  ∀                                                      Y                            <                            6                            >                                                                                              )                                        ⁢                                          ∀                                              (                                                  X                          <                          5                          >                                                                                                                                                                                                    ⁢                      ∀                          Y              <              5              >                                )                ⁢                  ∀                                    (                              X                <                4                >                                  ∀                                      Y                    <                    4                    >                                                              )                        ⁢                          ∀                                                (                                      X                    <                    3                    >                                          ∀                                              Y                        <                        3                        >                                                                              )                                ∀                                                                                    ⁢                              (                          X              <              2              >                              ∀                                  Y                  <                  2                  >                                                      )                    ⁢                      ∀                                          (                                  X                  <                  1                  >                                      ∀                                          Y                      <                      1                      >                                                                      )                            ⁢                              ∀                                  (                                      X                    <                    0                    >                    ∀                                                                                                                                                ⁢                          <              0              >                        )                    ]                ⁢                  ∀                      (                          C              <              7              >                              ∀                                  C                  <                  6                  >                                      ∀                                          C                      <                      5                      >                                              ∀                                                  C                          <                          4                          >                                                      ∀                                                          C                              <                              3                              >                                                                                                                                                                                                                                                          ⁢                      ∀                          C              <              2              >                              ∀                                  C                  <                  1                  >                                      ∀                                          C                      <                      0                      >                                                                                                    )                ]                                =                ⁢                                           ⋀                    ⁢                      [                          [                              (                                  X                  <                  7                  >                                      ∀                                          X                      <                      6                      >                                              ∀                                                  X                          <                          5                          >                                                      ∀                                                          X                              <                              4                              >                                                              ∀                                                                  X                                  <                                  3                                  >                                                                                                                                                                                                                                                                                                                                      ⁢                          ∀                              X                <                2                >                                  ∀                                      X                    <                    1                    >                                          ∀                                              X                        <                        0                        >                                                                                                                  )                    ]                ⁢                  ∀                      [                          (                              Y                <                7                >                                  ∀                                      Y                    <                    6                    >                                          ∀                      Y                                                                                                                                                      ⁢                      <            5            >                          ∀                              Y                <                4                >                                  ∀                                      Y                    <                    3                    >                                          ∀                                              Y                        <                        2                        >                                                  ∀                                                      Y                            <                            1                            >                                                          ∀                                                              Y                                <                                0                                >                                                                                                                                                                                                                                      )                ]                                        ⁢                  ∀                      (                          C              <              7              >                              ∀                                  C                  <                  6                  >                                      ∀                                          C                      <                      5                      >                                              ∀                                                  C                          <                          4                          >                                                      ∀                                                          C                              <                              3                              >                                                                                                                                                                                                                                                          ⁢                      ∀                          C              <              2              >                              ∀                                  C                  <                  1                  >                                      ∀                                          C                      <                      0                      >                                                                                                    )                ]                                =                ⁢                                           ⋀                    ⁢                      [                                                                               ⋀                                ⁢                XP                            ⁢                              ∀                                                                                                   ⋀                                        ⁢                    YP                                    ⁢                                      ∀                                          (                                              C                        <                        7                        >                                                  ∀                                                      C                            <                            6                            >                                                          ∀                                                              C                                <                                5                                >                                                                  ∀                                                                      <                                    4                                    >                                                                                                                                                                                                                                                                                                                                                          ⁢                      ∀                          C              <              3              >                              ∀                                  C                  <                  2                  >                                      ∀                                          C                      <                      1                      >                                              ∀                                                  C                          <                          0                          >                                                                                                                                                  )                ]            
Thus, the parity for the sum can be derived from the Excusive-OR of respective input parities and the Excusive-OR of carries to respective bits generated during the addition of the input data.
If P denotes a carry propagation condition and G denotes a carry generation condition for each input bit, the carry C is represented by:
                                                                                                                                                            C                        <                        7                        >=                                                ⁢                        G                        <                        6                        >                                                  +                          P                                                <                        6                        >                                            &                                        ⁢                    G                                    <                  5                  >                                      +                    P                                    <                  6                  >                                &                            ⁢              P                        <            5            >                    &                ⁢        G                                        ⁢                                                                                                                                                                                                      <                            4                            >                                                          +                              P                                                        <                            6                            >                                                    &                                                ⁢                        P                                            <                      5                      >                                        &                                    ⁢                  P                                <                4                >                            &                        ⁢            G                    <          3          >                      +            P                    <          6          >                                                ⁢                                                                                                                                                                                                                                                                                                                                          &                                    P                                                                    <                                  5                                  >                                                                &                                                            ⁢                              P                                                        <                            4                            >                                                    &                                                ⁢                        P                                            <                      3                      >                                        &                                    ⁢                  P                                <                2                >                            &                        ⁢            G                    <          1          >          +                                                ⁢                                                                                                                                                                                                                                                                                                                                          P                                    <                                    6                                    >                                                                    &                                                                ⁢                                P                                                            <                              5                              >                                                        &                                                    ⁢                          P                                                <                        4                        >                                            &                                        ⁢                    P                                    <                  3                  >                                &                            ⁢              P                        <            2            >                    &                                                ⁢                                                                                                                                                                                                                                    P                              <                              1                              >                                                        &                                                    ⁢                          G                                                <                        0                        >                                                  +                          P                                                <                        6                        >                                            &                                        ⁢                    P                                    <                  5                  >                                &                            ⁢              P                        <            4            >                    &                                                ⁢                                                                                                                                                                                                                                    P                              <                              3                              >                                                        &                                                    ⁢                          P                                                ⁢                                                                                                  <                        2                        >                                            &                                        ⁢                    P                                    <                  1                  >                                &                            ⁢              P                        <            0            >                          +              P                        <            6            >                    &                                                ⁢                                                                                                                                                                                                                                                                                                                                          P                                    <                                    5                                    >                                                                    &                                                                ⁢                                P                                                            <                              4                              >                                                        &                                                    ⁢                          P                                                <                        3                        >                                            &                                        ⁢                    P                                    <                  2                  >                                &                            ⁢              P                        <            1            >                    &                                                ⁢                                            P              <              0              >                        &                    ⁢          CIN                                                                                                                                                                                C                        <                        6                        >=                                                ⁢                        G                        <                        5                        >                                                  +                          P                                                <                        5                        >                                            &                                        ⁢                    G                                    <                  4                  >                                      +                    P                                    <                  5                  >                                &                            ⁢              P                        <            4            >                    &                ⁢        G                                        ⁢                                                                                                                                                                                                      <                            3                            >                                                          +                              P                                                        <                            5                            >                                                    &                                                ⁢                        P                                            <                      4                      >                                        &                                    ⁢                  P                                <                3                >                            &                        ⁢            G                    <          2          >                      +            P                                                          ⁢                                                                                                                                                                                                                                                                                                      <                                  5                                  >                                                                &                                                            ⁢                              P                                                        <                            4                            >                                                    &                                                ⁢                        P                                            <                      3                      >                                        &                                    ⁢                  P                                <                2                >                            &                        ⁢            G                    <          1          >                      +            P                                                          ⁢                                                                                                                                                                                                                                                                                                                                                                                <                                      5                                      >                                                                        &                                                                    ⁢                                  P                                                                <                                4                                >                                                            &                                                        ⁢                            P                                                    <                          3                          >                                                &                                            ⁢                      P                                        <                    2                    >                                    &                                ⁢                P                            <              1              >                        &                    ⁢          G                                                ⁢                                                                                                                                                                                                                                                                    <                                0                                >                                                                  +                                  P                                                                <                                5                                >                                                            &                                                        ⁢                            P                                                    <                          4                          >                                                &                                            ⁢                      P                                        <                    3                    >                                    &                                ⁢                P                            <              2              >                        &                    ⁢          P                                                ⁢                                                                                                  <                    1                    >                                    &                                ⁢                P                            <              0              >                        &                    ⁢          CIN                                                ⁢                  ⋮          ⁢                                          ⁢          ⋮                                                ⁢                  ⋮          ⁢                                          ⁢          ⋮                                                                                                                                                                                C                        <                        2                        >=                                                ⁢                        G                        <                        1                        >                                                  +                          P                                                <                        1                        >                                            &                                        ⁢                    G                                    <                  0                  >                                      +                    P                                    <                  1                  >                                &                            ⁢              P                        <            0            >                    &                ⁢        CIN                                                      C            <            1            >=                        ⁢            G            <            0            >                          +              P                        <            0            >                    &                ⁢        CIN                                C        <        0        >=                ⁢        CIN            CIN is equal to “1” if the averaging process is based on rounding off and “0” if it is based on rounding down.
P and G are represented by:P<n>=X<n>+Y<n>G<n>=X<n>&Y<n>
Thus, if logic corresponding to the Excusive-OR of the carries to respective bits is denoted by □, the following equation is given:ZP=^[^XP∀^YP]∀[X<7:0>□Y<7:0>]The logic □ is called Summed parity inversion prediction logic, and is complex as shown above. In this logic, the carry used to obtain the parity has the sole purpose of checking correctness of the adder and does not use the carry from the adder as it is. Rather, it requires a different circuit to obtain a carry from the inputs X<7:0> and Y<7:0>.
FIG. 9E illustrates an example of a conventional parity protected adder. XP<1:0> and YP<1:0> are 2-bit parities added to 16-bit input data X<15:00> and Y<15:00> on an 8-bit basis. A summed parity inversion prediction circuit 952 achieves the logic □ in the equation for obtaining ZP.
A parity protected adder 950 has a delay critical path, which begins from the input X, Y, then passes through the summed parity inversion prediction circuit 952 for the logic □, and finally enters Excusive-OR together with the result from Excusive-OR of input parities to output the parity ZP<1:0>.
Parity prediction logic in shift operation is explained next. If input data X<7:0> and its corresponding parity XP are given, the parity ZP for a shifted result Z can be derived from xor of input parity XP, shift-out data from parity unit of the input parity, and shift-in data.
Accordingly, the parity ZP of the result of shifting the input data X<7:0> to the right by one bit, can be obtained as follows.ZP=XP∀(“0”∀X<0>)
FIG. 9F illustrates an example of a conventional parity protected shifter. A parity protected shifter 960 includes a 1-bit-right shifter for 16-bit data and a shifted parity inversion prediction circuit 962. When 16-bit data X<15:00> is given parity XP<1:0>, the resultant parity ZP<1:0> can be derived from:ZP<1>=XP<1>∀X<8>ZP<0>=XP<0>∀X<8>∀X<0>
Thus, the conventional parity protected shifter 960 has a delay critical path, which subjects the input X<8:0> and the parity XP<1:0> to Excusive-OR to output the resultant parity ZP<1:0>.
A conventional averaging circuit with a parity prediction circuit that includes the parity protected adder 950 and the parity protected shifter 960 is explained next. FIG. 9G illustrates an example of a conventional averaging circuit that includes a parity prediction circuit.
The averaging circuit 970 obtains an average of two 16-bit input data X<15:00> and Y<15:00> by shifting the sum output from the adder 951 to the right by one bit using the 1-bit-right shifter 961.
An Excusive-OR of an output from the summed parity inversion prediction circuit 952, and input parity XP<1:0>, YP<1:0> is calculated. The Excusive-OR of this result and an output from the shifted parity inversion prediction circuit 962 gives the resultant parity ZP<1:0>.
As for the-average, it is sufficient to shift the sum output from the adder, by one bit. On the contrary, for the parity, it is required to execute Excusive-OR of the two input data and the input parity. Therefore, a delay critical path in the averaging circuit 970 includes calculation of the summed parity from input data in adding operation, input of the summed parity to the parity protected shifter, and output of the shifted parity.